import random

def isPowerOfTwo(n: int) -> bool:
    # 2**n 一定是只有一个1
    last_1 = n & (-n)
    return last_1 == n

def isPowerOfThree(n: int) -> bool:
    BIG_ONE = 3 ** 19   # 题目范围内最大的3的整数幂
    return n > 0 and BIG_ONE % n == 0   # 如果是，一定是刚好被除尽

def near2Power(n: int) -> int:
    if n <= 1: return 1
    n -= 1
    n |= n >> 1
    n |= n >> 2
    n |= n >> 4
    n |= n >> 8
    n |= n >> 16
    return n + 1
def near2Power2(n: int) -> int:
    if n <= 1: return 1
    while (last_1:=(n & (-n))) != n:
        n ^= last_1
    return n << 1

# https://leetcode.cn/problems/reverse-bits/description/
def reverseBits(n: int) -> int:
    # n = ((n & 0b10101010101010101010101010101010) >> 1) | ((n & 0b01010101010101010101010101010101) << 1)
    # n = ((n & 0b11001100110011001100110011001100) >> 2) | ((n & 0b00110011001100110011001100110011) << 2)
    # n = ((n & 0b11110000111100001111000011110000) >> 4) | ((n & 0b00001111000011110000111100001111) << 4)
    # n = ((n & 0b11111111000000001111111100000000) >> 8) | ((n & 0b00000000111111110000000011111111) << 8)
    # n = ((n & 0b11111111111111110000000000000000) >> 16) | ((n & 0b00000000000000001111111111111111) << 16)
    n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1)
    n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2)
    n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4)
    n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8)
    n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16)
    return n






def test_near2Power():
    for _ in range(1000):
        t = random.randint(1, 2<<32)
        r1 = near2Power(t)
        r2 = near2Power2(t)
        if r1 != r2:
            print(r1, r2, r1==r2)
    print("测试结束")